package sort.LeetCode;
//剑指 Offer 51. 数组中的逆序对
//有时间限制的，不然O(n^ 2) 肯定能完成

/*
public class 剑指offer_51_reversePairs {
    public static int conut = 0;
    public static int reversePairs(int[] nums) {
        mergeSortInternal(nums, 0, nums.length - 1);
        return conut;
    }

    */
/**
     * 在arr[l....r] 上进行归并排序
     *//*

    private static void mergeSortInternal(int[] arr, int l, int r) {

        if(l >= r){
            return;
        }


        int min = l + ((r - l) >> 1);//防止数据过大溢出，把多余部分除以 2就是一半的长度
        mergeSortInternal(arr,l, min);
        mergeSortInternal(arr,min + 1, r);
        //此时数组arr【l..min） 和 arr【min + 1 .... r）已经分别有序 只剩下合并两个数组


         merge(arr, l, min, r);

//        if(arr[min] > arr[min + 1]){
//            merge(arr, l, min, r);
//        }

    }

    */
/**
     * 将有序子数组arr[l..mid] 和 有序arr[mid + 1...r] 合并为一个大的有序数组arr[l..r]
     * 将两个有序的子数组合并成一个大的有效数组
     *//*

    private static void merge(int[] arr, int l, int min, int r) {
        int[] aux = new int[r - l + 1];//创建一个l。。r范围等长的数组

        for (int i = 0; i < aux.length; i++) {
            aux[i] = arr[i + l];
        }
        int i = l;

        int j = min + 1;


        for (int k = l; k <= r; k++) {

            if(i > min){
                //第一个数组已经遍历完毕
                arr[k] = aux[j - l];
                j ++;
            }else if(j > r){
                //第二个数组已经遍历完毕
                arr[k] = aux[i - l];
                i ++;
            }else if(aux[i - l] <= aux[j - l]){ //这里要 减去 偏移量 l才是aux数组的索引
                //左数组此刻元素 小于 右数组此刻元素
                arr[k] = aux[i - l];
                i ++;
            }else{

                    conut += (min - i + 1);

                //左数组此刻元素 大于 右数组此刻元素
                arr[k] = aux[j - l];
                j ++;

            }

        }

    }


    public static void main(String[] args) {
        int[] arr = {1,1,1,1,1};
        int t = reversePairs(arr);
        System.out.println(t);

    }
}
*/

//自己再写一遍归并  这个效率更快
public class 剑指offer_51_reversePairs {
    public  int reversePairs(int[] nums) {
        return mergeSortInternal(nums, 0, nums.length - 1);
    }

    /**
     * 传入数组，完成归并过程，并返回其中的逆序对
     */
    private int mergeSortInternal(int[] nums, int l, int r) {
        if(l >= r){
            return 0;
        }

        int min = l + ( (r - l) >> 1 );//中间索引
        int left = mergeSortInternal(nums, l, min);
        int right = mergeSortInternal(nums, min + 1, r);

        if(nums[min] > nums[min + 1]){

            return merge(nums, l, min,  r) + left + right;
        }
        return left + right;
    }

    /**
     * 给你一个数组，完成合并数组的操作，并返回逆序对
     */
    private int merge(int[] nums, int l, int min,  int r) {
        int[] aux = new int[r - l + 1];
        for (int i = l; i <= r; i++) {
                aux[i - l] = nums[i];
        }
        //完成合并数组的操作
        int left = l;//第一个数组的标记
        int right = min + 1;//第二个数组的标记
        int conut = 0;//统计逆序对
        for (int i = l; i <= r ; i++) {
             if(left > min){
                 //表示第一个数组已经走完了
                 nums[i] = aux[right - l];
                 right ++;
             }else if(right > r){
                 //表示第二个数组已经走完了
                 nums[i] = aux[left - l];
                 left ++;
             }else if (aux[left - l] <= aux[right - l]){
                 //表示第一个数组标记元素小于第二个数组元素
                 nums[i] = aux[left - l];
                 left ++;
             }else {
                 //表示第一个数组标记元素大于第二个数组元素
                 conut += min - left + 1;
                 nums[i] = aux[right - l];
                 right ++;
             }

        }
        return conut;
    }

}